/*
	解法：使用unordered_map数据结构
	为什么：只关心字符频次，而不关心字符顺序
	时间复杂度：O(m + n)，空间复杂度：O(1)
 */

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

class Solution
{
public:
	bool canConstruct(string ransomNote, string magazine)
	{
		unordered_map<char, int> charCount;
		// 统计 magazine 中每个字符出现的次数
		for (int i = 0; i < (int)magazine.length(); i++)
		{
			char c = magazine[i];
			charCount[c]++;
		}
		
		// 检查 ransomNote 中的字符是否能被 magazine 提供
		for (int i = 0; i < (int)ransomNote.length(); i++)
		{
			char c = ransomNote[i];
			charCount[c]--;
			if (charCount[c] < 0)
			{
				return false;
			}
		}
		
		return true;
	}
};

int main()
{
	Solution s;
	string ransomNote, magazine;

	cout << "请输入 ransomNote 字符串: ";
	cin >> ransomNote;

}

int main()
{
	Solution s;
	string ransomNote, magazine;
	
	cout << "请输入 ransomNote 字符串: ";
	cin >> ransomNote;
	
	cout << "请输入 magazine 字符串: ";
	cin >> magazine;
	
	if (s.canConstruct(ransomNote, magazine))
	{
		cout << "true" << endl;
	}
	else
	{
		cout << "false" << endl;
	}
	
	return 0;
}




